Merkle Mountain Range
Merkle treeがバランスの取れた2分木であるのに対して、Merkle Mountain Range (以下MMR) はバランスの取れた2分木のリストか、右上から切り捨てられた1本の2分木とみなす 基本的には追加のみ
https://scrapbox.io/files/651e9e7f2d9bdf001b4694c1.png
上記の図の場合はleafが11でsizeが19になっており、番号は挿入順
要素は左から右に追加され、2つの子が存在するとすぐに親が追加される
ex. 0と1が追加されたら親である2を追加する / 3と4を追加したら親である5を追加し、さらに2と5の親である6を追加する
ハッシュ
子ノードのハッシュ
データDを格納するindexnのleafl
Node(l) = Hash(n | D)
親ノードのハッシュ
インデックスmにある任意の親pについて
Node(p) = Hash(m | Node(left_child(p)) | Node(right_child(p)))
このプロセスをbagging the peaksと呼ぶ
Bagging the peaks
1. MMRのpeakの特定
https://scrapbox.io/files/651ea5e8fb007f001c78ccd0.png
このMMRは11個のノードを持ち、そのpeakは111 (7)、1010 (10)、1011 (11)にある
ピークは$ 2^n - 1の形をした位置を持ち、常にMMRの内部にある最大の位置となる
サイズが11のMMRに対して以下の計算を繰り返し行う
https://scrapbox.io/files/651ea7bd60a189001c16bedd.png
この計算によって最初のpeakが7(111)であることが分かる
2. 次のpeakの特定
右のsiblingsにjumpする
そのノードがMMRになければ、その左の子を取る
その子もMMRになければ、MMRに存在するノードができるまでその左の子を取り続ける
次のピークを見つけたら、最後のノードにたどり着くまでこのプロセスを繰り返す
高さ$ hのノードの右の兄弟にジャンプすることは、その位置に$ 2^{(h+1)}-1を足すこと
その左の子を取ることは$ 2^hを引くこと
3. 一番上のpeakを得る
3つのピークp1,p2,p3を持つサイズNのMMRの場合、最終的に一番上のピークが得られる
P = Hash(N | Hash(N | Node(p3) | Node(p2)) | Node(p1))
MMRのMerkle proof
ex. MMRのitemの1つであるOutXを証明する
Merkle proofの構成要素
OutXを示すleaf nodeのhash
ツリーの全体のrootのhash
すべてのMMR peakを表すhashのリスト
一緒にhash化すると全体のrootと一致する
OutXからそのpeakへの分岐を構成するsibling hashのリスト
ブランチを正しく再構築するためのsiblingの位置 (左 / 右) のリスト
Merkle proofで証明できること
peakの下にnodeが含まれていることを証明する
peakが組み合わさって全体のroot hashを形成していることを証明する
utxo rootがMerkle proofのrootと一致することを検証することで、与えられたblock headerの(未使用の)出力が含まれることを証明する
あるblock headerで出力が未使用であれば、それは少なくともそのブロックと同じくらい古い
参考資料